<html>
<head>
<meta http-equiv="Content-Type" content="text/html; charset=US-ASCII">
<title>Addition</title>
<link rel="stylesheet" href="../../../../../../doc/src/boostbook.css" type="text/css">
<meta name="generator" content="DocBook XSL Stylesheets V1.74.0">
<link rel="home" href="../../index.html" title="Chapter&#160;1.&#160;Boost.Icl">
<link rel="up" href="../function_reference.html" title="Function Reference">
<link rel="prev" href="selection.html" title="Selection">
<link rel="next" href="subtraction.html" title="Subtraction">
</head>
<body bgcolor="white" text="black" link="#0000FF" vlink="#840084" alink="#0000FF">
<table cellpadding="2" width="100%"><tr>
<td valign="top"><img alt="Boost C++ Libraries" width="277" height="86" src="../../../../../../boost.png"></td>
<td align="center"><a href="../../../../../../index.html">Home</a></td>
<td align="center"><a href="../../../../../libraries.htm">Libraries</a></td>
<td align="center"><a href="http://www.boost.org/users/people.html">People</a></td>
<td align="center"><a href="http://www.boost.org/users/faq.html">FAQ</a></td>
<td align="center"><a href="../../../../../../more/index.htm">More</a></td>
</tr></table>
<hr>
<div class="spirit-nav">
<a accesskey="p" href="selection.html"><img src="../../../../../../doc/src/images/prev.png" alt="Prev"></a><a accesskey="u" href="../function_reference.html"><img src="../../../../../../doc/src/images/up.png" alt="Up"></a><a accesskey="h" href="../../index.html"><img src="../../../../../../doc/src/images/home.png" alt="Home"></a><a accesskey="n" href="subtraction.html"><img src="../../../../../../doc/src/images/next.png" alt="Next"></a>
</div>
<div class="section boost_icl_function_reference_addition" lang="en">
<div class="titlepage"><div><div><h3 class="title">
<a name="boost_icl.function_reference.addition"></a><a class="link" href="addition.html" title="Addition">Addition</a>
</h3></div></div></div>
<div class="toc"><dl>
<dt><span class="section"><a href="addition.html#boost_icl.function_reference.addition.synopsis">Synopsis</a></span></dt>
<dt><span class="section"><a href="addition.html#boost_icl.function_reference.addition.functions">Functions</a></span></dt>
<dt><span class="section"><a href="addition.html#boost_icl.function_reference.addition.inplace_operators">Inplace
        operators</a></span></dt>
<dt><span class="section"><a href="addition.html#boost_icl.function_reference.addition.infix_operators">Infix
        operators</a></span></dt>
</dl></div>
<div class="section boost_icl_function_reference_addition_synopsis" lang="en">
<div class="titlepage"><div><div><h4 class="title">
<a name="boost_icl.function_reference.addition.synopsis"></a><a class="link" href="addition.html#boost_icl.function_reference.addition.synopsis" title="Synopsis">Synopsis</a>
</h4></div></div></div>
<div class="informaltable"><table class="table">
<colgroup>
<col>
<col>
<col>
<col>
<col>
</colgroup>
<thead><tr>
<th>
                <p>
                  Addition
                </p>
                </th>
<th>
                <p>
                  interval<br> sets
                </p>
                </th>
<th>
                <p>
                  interval<br> maps
                </p>
                </th>
<th>
                <p>
                  element<br> sets
                </p>
                </th>
<th>
                <p>
                  element<br> maps
                </p>
                </th>
</tr></thead>
<tbody>
<tr>
<td>
                <p>
                  <code class="computeroutput"><span class="identifier">T</span><span class="special">&amp;</span>
                  <span class="identifier">T</span><span class="special">::</span><span class="identifier">add</span><span class="special">(</span><span class="keyword">const</span> <span class="identifier">P</span><span class="special">&amp;)</span></code>
                </p>
                </td>
<td>
                <p>
                  <a class="link" href="../interface/function_synopsis.html#element_type"><span class="bold"><strong>e</strong></span></a>
                  <a class="link" href="../interface/function_synopsis.html#interval_type"><span class="bold"><strong>i</strong></span></a>
                </p>
                </td>
<td>
                <p>
                  <a class="link" href="../interface/function_synopsis.html#element_mapping_type"><span class="bold"><strong>b</strong></span></a>
                  <a class="link" href="../interface/function_synopsis.html#interval_mapping_type"><span class="bold"><strong>p</strong></span></a>
                </p>
                </td>
<td>
                <p>
                </p>
                </td>
<td>
                <p>
                  <a class="link" href="../interface/function_synopsis.html#element_mapping_type"><span class="bold"><strong>b</strong></span></a>
                </p>
                </td>
</tr>
<tr>
<td>
                <p>
                  <code class="computeroutput"><span class="identifier">T</span><span class="special">&amp;</span>
                  <span class="identifier">add</span><span class="special">(</span><span class="identifier">T</span><span class="special">&amp;,</span>
                  <span class="keyword">const</span> <span class="identifier">P</span><span class="special">&amp;)</span></code>
                </p>
                </td>
<td>
                <p>
                  <a class="link" href="../interface/function_synopsis.html#element_type"><span class="bold"><strong>e</strong></span></a>
                  <a class="link" href="../interface/function_synopsis.html#interval_type"><span class="bold"><strong>i</strong></span></a>
                </p>
                </td>
<td>
                <p>
                  <a class="link" href="../interface/function_synopsis.html#element_mapping_type"><span class="bold"><strong>b</strong></span></a>
                  <a class="link" href="../interface/function_synopsis.html#interval_mapping_type"><span class="bold"><strong>p</strong></span></a>
                </p>
                </td>
<td>
                <p>
                  <a class="link" href="../interface/function_synopsis.html#element_type"><span class="bold"><strong>e</strong></span></a>
                </p>
                </td>
<td>
                <p>
                  <a class="link" href="../interface/function_synopsis.html#element_mapping_type"><span class="bold"><strong>b</strong></span></a>
                </p>
                </td>
</tr>
<tr>
<td>
                <p>
                  <code class="computeroutput"><span class="identifier">J</span> <span class="identifier">T</span><span class="special">::</span><span class="identifier">add</span><span class="special">(</span><span class="identifier">J</span>
                  <span class="identifier">pos</span><span class="special">,</span>
                  <span class="keyword">const</span> <span class="identifier">P</span><span class="special">&amp;)</span></code>
                </p>
                </td>
<td>
                <p>
                  <a class="link" href="../interface/function_synopsis.html#interval_type"><span class="bold"><strong>i</strong></span></a>
                </p>
                </td>
<td>
                <p>
                  <a class="link" href="../interface/function_synopsis.html#interval_mapping_type"><span class="bold"><strong>p</strong></span></a>
                </p>
                </td>
<td>
                <p>
                </p>
                </td>
<td>
                <p>
                  <a class="link" href="../interface/function_synopsis.html#element_mapping_type"><span class="bold"><strong>b</strong></span></a>
                </p>
                </td>
</tr>
<tr>
<td>
                <p>
                  <code class="computeroutput"><span class="identifier">J</span> <span class="identifier">add</span><span class="special">(</span><span class="identifier">T</span><span class="special">&amp;,</span> <span class="identifier">J</span>
                  <span class="identifier">pos</span><span class="special">,</span>
                  <span class="keyword">const</span> <span class="identifier">P</span><span class="special">&amp;)</span></code>
                </p>
                </td>
<td>
                <p>
                  <a class="link" href="../interface/function_synopsis.html#interval_type"><span class="bold"><strong>i</strong></span></a>
                </p>
                </td>
<td>
                <p>
                  <a class="link" href="../interface/function_synopsis.html#interval_mapping_type"><span class="bold"><strong>p</strong></span></a>
                </p>
                </td>
<td>
                <p>
                  <a class="link" href="../interface/function_synopsis.html#element_type"><span class="bold"><strong>e</strong></span></a>
                </p>
                </td>
<td>
                <p>
                  <a class="link" href="../interface/function_synopsis.html#element_mapping_type"><span class="bold"><strong>b</strong></span></a>
                </p>
                </td>
</tr>
<tr>
<td>
                <p>
                  <code class="computeroutput"><span class="identifier">T</span><span class="special">&amp;</span>
                  <span class="keyword">operator</span> <span class="special">+=(</span><span class="identifier">T</span><span class="special">&amp;,</span>
                  <span class="keyword">const</span> <span class="identifier">P</span><span class="special">&amp;)</span></code>
                </p>
                </td>
<td>
                <p>
                  <a class="link" href="../interface/function_synopsis.html#element_type"><span class="bold"><strong>e</strong></span></a>
                  <a class="link" href="../interface/function_synopsis.html#interval_type"><span class="bold"><strong>i</strong></span></a>
                  <a class="link" href="../interface/function_synopsis.html#interval_set_types"><span class="bold"><strong>S</strong></span></a>
                </p>
                </td>
<td>
                <p>
                  <a class="link" href="../interface/function_synopsis.html#element_mapping_type"><span class="bold"><strong>b</strong></span></a>
                  <a class="link" href="../interface/function_synopsis.html#interval_mapping_type"><span class="bold"><strong>p</strong></span></a>
                  <a class="link" href="../interface/function_synopsis.html#interval_map_types"><span class="bold"><strong>M</strong></span></a>
                </p>
                </td>
<td>
                <p>
                  <a class="link" href="../interface/function_synopsis.html#element_type"><span class="bold"><strong>e</strong></span></a>
                  <a class="link" href="../interface/function_synopsis.html#itl_set_type"><span class="bold"><strong>s</strong></span></a>
                </p>
                </td>
<td>
                <p>
                  <a class="link" href="../interface/function_synopsis.html#element_mapping_type"><span class="bold"><strong>b</strong></span></a>
                  <a class="link" href="../interface/function_synopsis.html#itl_map_type"><span class="bold"><strong>m</strong></span></a>
                </p>
                </td>
</tr>
<tr>
<td>
                <p>
                  <code class="computeroutput"><span class="identifier">T</span> <span class="keyword">operator</span>
                  <span class="special">+</span> <span class="special">(</span><span class="identifier">T</span><span class="special">,</span>
                  <span class="keyword">const</span> <span class="identifier">P</span><span class="special">&amp;)</span></code><br> <code class="computeroutput"><span class="identifier">T</span>
                  <span class="keyword">operator</span> <span class="special">+</span>
                  <span class="special">(</span><span class="keyword">const</span>
                  <span class="identifier">P</span><span class="special">&amp;,</span>
                  <span class="identifier">T</span><span class="special">)</span></code>
                </p>
                </td>
<td>
                <p>
                  <a class="link" href="../interface/function_synopsis.html#element_type"><span class="bold"><strong>e</strong></span></a>
                  <a class="link" href="../interface/function_synopsis.html#interval_type"><span class="bold"><strong>i</strong></span></a>
                  <a class="link" href="../interface/function_synopsis.html#interval_set_types"><span class="bold"><strong>S</strong></span></a>
                </p>
                </td>
<td>
                <p>
                  <a class="link" href="../interface/function_synopsis.html#element_mapping_type"><span class="bold"><strong>b</strong></span></a>
                  <a class="link" href="../interface/function_synopsis.html#interval_mapping_type"><span class="bold"><strong>p</strong></span></a>
                  <a class="link" href="../interface/function_synopsis.html#interval_map_types"><span class="bold"><strong>M</strong></span></a>
                </p>
                </td>
<td>
                <p>
                  <a class="link" href="../interface/function_synopsis.html#element_type"><span class="bold"><strong>e</strong></span></a>
                  <a class="link" href="../interface/function_synopsis.html#itl_set_type"><span class="bold"><strong>s</strong></span></a>
                </p>
                </td>
<td>
                <p>
                  <a class="link" href="../interface/function_synopsis.html#element_mapping_type"><span class="bold"><strong>b</strong></span></a>
                  <a class="link" href="../interface/function_synopsis.html#itl_map_type"><span class="bold"><strong>m</strong></span></a>
                </p>
                </td>
</tr>
<tr>
<td>
                <p>
                  <code class="computeroutput"><span class="identifier">T</span><span class="special">&amp;</span>
                  <span class="keyword">operator</span> <span class="special">|=(</span>
                  <span class="identifier">T</span><span class="special">&amp;,</span>
                  <span class="keyword">const</span> <span class="identifier">P</span><span class="special">&amp;)</span></code>
                </p>
                </td>
<td>
                <p>
                  <a class="link" href="../interface/function_synopsis.html#element_type"><span class="bold"><strong>e</strong></span></a>
                  <a class="link" href="../interface/function_synopsis.html#interval_type"><span class="bold"><strong>i</strong></span></a>
                  <a class="link" href="../interface/function_synopsis.html#interval_set_types"><span class="bold"><strong>S</strong></span></a>
                </p>
                </td>
<td>
                <p>
                  <a class="link" href="../interface/function_synopsis.html#element_mapping_type"><span class="bold"><strong>b</strong></span></a>
                  <a class="link" href="../interface/function_synopsis.html#interval_mapping_type"><span class="bold"><strong>p</strong></span></a>
                  <a class="link" href="../interface/function_synopsis.html#interval_map_types"><span class="bold"><strong>M</strong></span></a>
                </p>
                </td>
<td>
                <p>
                  <a class="link" href="../interface/function_synopsis.html#element_type"><span class="bold"><strong>e</strong></span></a>
                  <a class="link" href="../interface/function_synopsis.html#itl_set_type"><span class="bold"><strong>s</strong></span></a>
                </p>
                </td>
<td>
                <p>
                  <a class="link" href="../interface/function_synopsis.html#element_mapping_type"><span class="bold"><strong>b</strong></span></a>
                  <a class="link" href="../interface/function_synopsis.html#itl_map_type"><span class="bold"><strong>m</strong></span></a>
                </p>
                </td>
</tr>
<tr>
<td>
                <p>
                  <code class="computeroutput"><span class="identifier">T</span> <span class="keyword">operator</span>
                  <span class="special">|</span> <span class="special">(</span><span class="identifier">T</span><span class="special">,</span>
                  <span class="keyword">const</span> <span class="identifier">P</span><span class="special">&amp;)</span></code><br> <code class="computeroutput"><span class="identifier">T</span>
                  <span class="keyword">operator</span> <span class="special">|</span>
                  <span class="special">(</span><span class="keyword">const</span>
                  <span class="identifier">P</span><span class="special">&amp;,</span>
                  <span class="identifier">T</span><span class="special">)</span></code>
                </p>
                </td>
<td>
                <p>
                  <a class="link" href="../interface/function_synopsis.html#element_type"><span class="bold"><strong>e</strong></span></a>
                  <a class="link" href="../interface/function_synopsis.html#interval_type"><span class="bold"><strong>i</strong></span></a>
                  <a class="link" href="../interface/function_synopsis.html#interval_set_types"><span class="bold"><strong>S</strong></span></a>
                </p>
                </td>
<td>
                <p>
                  <a class="link" href="../interface/function_synopsis.html#element_mapping_type"><span class="bold"><strong>b</strong></span></a>
                  <a class="link" href="../interface/function_synopsis.html#interval_mapping_type"><span class="bold"><strong>p</strong></span></a>
                  <a class="link" href="../interface/function_synopsis.html#interval_map_types"><span class="bold"><strong>M</strong></span></a>
                </p>
                </td>
<td>
                <p>
                  <a class="link" href="../interface/function_synopsis.html#element_type"><span class="bold"><strong>e</strong></span></a>
                  <a class="link" href="../interface/function_synopsis.html#itl_set_type"><span class="bold"><strong>s</strong></span></a>
                </p>
                </td>
<td>
                <p>
                  <a class="link" href="../interface/function_synopsis.html#element_mapping_type"><span class="bold"><strong>b</strong></span></a>
                  <a class="link" href="../interface/function_synopsis.html#itl_map_type"><span class="bold"><strong>m</strong></span></a>
                </p>
                </td>
</tr>
</tbody>
</table></div>
<p>
          Functions and operators that implement <span class="emphasis"><em><span class="bold"><strong>Addition</strong></span></em></span>
          on <span class="bold"><strong>icl</strong></span> objects are given in the table
          above. <code class="computeroutput"><span class="keyword">operator</span> <span class="special">|=</span></code>
          and <code class="computeroutput"><span class="keyword">operator</span> <span class="special">|</span></code>
          are behavioral identical to <code class="computeroutput"><span class="keyword">operator</span>
          <span class="special">+=</span></code> and <code class="computeroutput"><span class="keyword">operator</span>
          <span class="special">+</span></code>. This is a redundancy that has
          been introduced deliberately, because a <span class="emphasis"><em>set union</em></span>
          semantics is often attached <code class="computeroutput"><span class="identifier">operators</span>
          <span class="special">|=</span></code> and <code class="computeroutput"><span class="special">|</span></code>.
        </p>
<div class="informaltable"><table class="table">
<colgroup>
<col>
<col>
</colgroup>
<thead><tr>
<th>
                <p>
                </p>
                </th>
<th>
                <p>
                  Description of Addition
                </p>
                </th>
</tr></thead>
<tbody>
<tr>
<td>
                <p>
                  <code class="computeroutput"><span class="identifier">Sets</span></code>
                </p>
                </td>
<td>
                <p>
                  Addition on Sets implements <span class="emphasis"><em><span class="bold"><strong>set
                  union</strong></span></em></span>
                </p>
                </td>
</tr>
<tr>
<td>
                <p>
                  <code class="computeroutput"><span class="identifier">Maps</span></code>
                </p>
                </td>
<td>
                <p>
                  Addition on Maps implements a <span class="emphasis"><em><span class="bold"><strong>map
                  union</strong></span></em></span> function similar to <span class="emphasis"><em>set union</em></span>.
                  If, on insertion of an element value pair <code class="computeroutput"><span class="special">(</span><span class="identifier">k</span><span class="special">,</span><span class="identifier">v</span><span class="special">)</span></code>
                  it's key <code class="computeroutput"><span class="identifier">k</span></code> is in
                  the map already, the addition function is propagated to the associated
                  value. This functionality has been introduced as <span class="emphasis"><em>aggregate
                  on collision</em></span> for element maps and <span class="emphasis"><em>aggregate
                  on overlap</em></span> for interval maps.
                </p>
                <p>
                  Find more on <a class="link" href="../concepts/aggrovering.html" title="Addability, Subtractability and Aggregate on Overlap"><span class="emphasis"><em>addability
                  of maps</em></span></a> and related <a class="link" href="../semantics/maps.html" title="Maps"><span class="emphasis"><em>semantic
                  issues</em></span></a> following the links.
                </p>
                <p>
                  Examples, demonstrating Addition on interval containers are <a class="link" href="../examples/overlap_counter.html" title="Overlap counter"><span class="emphasis"><em>overlap
                  counter</em></span></a>, <a class="link" href="../examples/party.html" title="Party"><span class="emphasis"><em>party</em></span></a>
                  and <a class="link" href="../examples/partys_height_average.html" title="Party's height average"><span class="emphasis"><em>party's
                  height average.</em></span></a>
                </p>
                </td>
</tr>
</tbody>
</table></div>
<p>
          For <code class="computeroutput"><span class="identifier">Sets</span></code> <span class="emphasis"><em><span class="bold"><strong>addition</strong></span></em></span> and <span class="emphasis"><em><span class="bold"><strong>insertion</strong></span></em></span>
          are implemented identically. Functions <code class="computeroutput"><span class="identifier">add</span></code>
          and <code class="computeroutput"><span class="identifier">insert</span></code> collapse to
          the same function. For <code class="computeroutput"><span class="identifier">Maps</span></code>
          <span class="emphasis"><em><span class="bold"><strong>addition</strong></span></em></span> and <span class="emphasis"><em><span class="bold"><strong>insertion</strong></span></em></span> work differently. Function
          <code class="computeroutput"><span class="identifier">add</span></code> performs aggregations
          on collision or overlap, while function <code class="computeroutput"><span class="identifier">insert</span></code>
          only inserts values that do not yet have key values.
        </p>
</div>
<div class="section boost_icl_function_reference_addition_functions" lang="en">
<div class="titlepage"><div><div><h4 class="title">
<a name="boost_icl.function_reference.addition.functions"></a><a class="link" href="addition.html#boost_icl.function_reference.addition.functions" title="Functions">Functions</a>
</h4></div></div></div>
<p>
          The admissible combinations of types for member function <code class="computeroutput"><span class="identifier">T</span><span class="special">&amp;</span> <span class="identifier">T</span><span class="special">::</span><span class="identifier">add</span><span class="special">(</span><span class="keyword">const</span> <span class="identifier">P</span><span class="special">&amp;)</span></code>
          can be summarized in the <span class="emphasis"><em><span class="bold"><strong>overload table</strong></span></em></span>
          below:
        </p>
<p>
          
</p>
<pre class="programlisting"><span class="comment">// overload table for    T\P| e i b p  
</span><span class="identifier">T</span><span class="special">&amp;</span> <span class="identifier">T</span><span class="special">::</span><span class="identifier">add</span><span class="special">(</span><span class="keyword">const</span> <span class="identifier">P</span><span class="special">&amp;)</span>      <span class="special">---+--------</span>
<span class="identifier">T</span><span class="special">&amp;</span> <span class="identifier">add</span><span class="special">(</span><span class="identifier">T</span><span class="special">&amp;,</span> <span class="keyword">const</span> <span class="identifier">P</span><span class="special">&amp;)</span>      <span class="identifier">s</span> <span class="special">|</span> <span class="identifier">s</span>
                          <span class="identifier">m</span> <span class="special">|</span>     <span class="identifier">m</span>
                          <span class="identifier">S</span> <span class="special">|</span> <span class="identifier">S</span> <span class="identifier">S</span>      
                          <span class="identifier">M</span> <span class="special">|</span>     <span class="identifier">M</span> <span class="identifier">M</span>  
</pre>
<p>
        </p>
<p>
          The next table contains complexity characteristics for <code class="computeroutput"><span class="identifier">add</span></code>.
        </p>
<div class="table">
<a name="id1155216"></a><p class="title"><b>Table&#160;1.21.&#160;Time Complexity for member function add on icl
        containers</b></p>
<div class="table-contents"><table class="table" summary="Time Complexity for member function add on icl
        containers">
<colgroup>
<col>
<col>
<col>
<col>
<col>
</colgroup>
<thead><tr>
<th>
              <p>
                <code class="computeroutput"><span class="identifier">T</span><span class="special">&amp;</span>
                <span class="identifier">T</span><span class="special">::</span><span class="identifier">add</span><span class="special">(</span><span class="keyword">const</span> <span class="identifier">P</span><span class="special">&amp;)</span></code><br> <code class="computeroutput"><span class="identifier">T</span><span class="special">&amp;</span> <span class="identifier">add</span><span class="special">(</span><span class="identifier">T</span><span class="special">&amp;,</span> <span class="keyword">const</span>
                <span class="identifier">P</span><span class="special">&amp;)</span></code>
              </p>
              </th>
<th>
              <p>
                domain<br> type
              </p>
              </th>
<th>
              <p>
                interval<br> type
              </p>
              </th>
<th>
              <p>
                domain<br> mapping<br> type
              </p>
              </th>
<th>
              <p>
                interval<br> mapping<br> type
              </p>
              </th>
</tr></thead>
<tbody>
<tr>
<td>
              <p>
                <a href="http://www.cplusplus.com/reference/stl/set/" target="_top"><code class="computeroutput"><span class="identifier">std</span><span class="special">::</span><span class="identifier">set</span></code> </a>
              </p>
              </td>
<td>
              <p>
                <span class="emphasis"><em>O(log n)</em></span>
              </p>
              </td>
<td>
              <p>
              </p>
              </td>
<td>
              <p>
              </p>
              </td>
<td>
              <p>
              </p>
              </td>
</tr>
<tr>
<td>
              <p>
                <code class="computeroutput"><a class="link" href="../../boost/icl/map.html" title="Class template map">icl::map</a></code>
              </p>
              </td>
<td>
              <p>
              </p>
              </td>
<td>
              <p>
              </p>
              </td>
<td>
              <p>
                <span class="emphasis"><em>O(log n)</em></span>
              </p>
              </td>
<td>
              <p>
              </p>
              </td>
</tr>
<tr>
<td>
              <p>
                <code class="computeroutput"><a class="link" href="../../boost/icl/interval_set.html" title="Class template interval_set">interval_set</a></code><br>
                <code class="computeroutput"><a class="link" href="../../boost/icl/separate_interval_set.html" title="Class template separate_interval_set">separate_interval_set</a></code>
              </p>
              </td>
<td>
              <p>
                <span class="emphasis"><em>O(log n)</em></span>
              </p>
              </td>
<td>
              <p>
                <span class="emphasis"><em>amortized<br> O(log n)</em></span>
              </p>
              </td>
<td>
              <p>
              </p>
              </td>
<td>
              <p>
              </p>
              </td>
</tr>
<tr>
<td>
              <p>
                <code class="computeroutput"><a class="link" href="../../boost/icl/split_interval_set.html" title="Class template split_interval_set">split_interval_set</a></code>
              </p>
              </td>
<td>
              <p>
                <span class="emphasis"><em>O(log n)</em></span>
              </p>
              </td>
<td>
              <p>
                <span class="emphasis"><em>O(n)</em></span>
              </p>
              </td>
<td>
              <p>
              </p>
              </td>
<td>
              <p>
              </p>
              </td>
</tr>
<tr>
<td>
              <p>
                <code class="computeroutput"><a class="link" href="../../boost/icl/interval_map.html" title="Class template interval_map">interval_map</a></code><br>
                <code class="computeroutput"><a class="link" href="../../boost/icl/split_interval_map.html" title="Class template split_interval_map">split_interval_map</a></code>
              </p>
              </td>
<td>
              <p>
              </p>
              </td>
<td>
              <p>
              </p>
              </td>
<td>
              <p>
                <span class="emphasis"><em>O(log n)</em></span>
              </p>
              </td>
<td>
              <p>
                <span class="emphasis"><em>O(n)</em></span>
              </p>
              </td>
</tr>
</tbody>
</table></div>
</div>
<br class="table-break"><a name="boost_icl.function_reference.addition.functions.hinted_addition"></a><h6>
<a name="id1155640"></a>
          <a class="link" href="addition.html#boost_icl.function_reference.addition.functions.hinted_addition">Hinted
          addition</a>
        </h6>
<p>
          Function <code class="computeroutput"><span class="identifier">J</span> <span class="identifier">T</span><span class="special">::</span><span class="identifier">add</span><span class="special">(</span><span class="identifier">J</span> <span class="identifier">prior</span><span class="special">,</span> <span class="keyword">const</span> <span class="identifier">P</span><span class="special">&amp;</span> <span class="identifier">addend</span><span class="special">)</span></code>
          allows for an addition in <span class="emphasis"><em><span class="bold"><strong>constant time</strong></span></em></span>,
          if <code class="computeroutput"><span class="identifier">addend</span></code> can be inserted
          right after iterator <code class="computeroutput"><span class="identifier">prior</span></code>
          without collision. If this is not possible the complexity characteristics
          are as stated for the non hinted addition above. Hinted addition is available
          for these combinations of types: 
</p>
<pre class="programlisting"><span class="comment">// overload table for addition with hint        T\P| e i b p   
</span><span class="identifier">J</span> <span class="identifier">T</span><span class="special">::</span><span class="identifier">add</span><span class="special">(</span><span class="identifier">J</span> <span class="identifier">prior</span><span class="special">,</span> <span class="keyword">const</span> <span class="identifier">P</span><span class="special">&amp;)</span>                     <span class="special">---+--------</span>
<span class="identifier">J</span> <span class="identifier">add</span><span class="special">(</span><span class="identifier">T</span><span class="special">&amp;,</span> <span class="identifier">J</span> <span class="identifier">prior</span><span class="special">,</span> <span class="keyword">const</span> <span class="identifier">P</span><span class="special">&amp;)</span>                     <span class="identifier">s</span> <span class="special">|</span> <span class="identifier">s</span>
                                                 <span class="identifier">m</span> <span class="special">|</span>     <span class="identifier">m</span>
                                                 <span class="identifier">S</span> <span class="special">|</span>   <span class="identifier">S</span>      
                                                 <span class="identifier">M</span> <span class="special">|</span>       <span class="identifier">M</span>   
</pre>
<p>
        </p>
</div>
<div class="section boost_icl_function_reference_addition_inplace_operators" lang="en">
<div class="titlepage"><div><div><h4 class="title">
<a name="boost_icl.function_reference.addition.inplace_operators"></a><a class="link" href="addition.html#boost_icl.function_reference.addition.inplace_operators" title="Inplace operators">Inplace
        operators</a>
</h4></div></div></div>
<p>
          The possible overloads of inplace <code class="computeroutput"><span class="identifier">T</span><span class="special">&amp;</span> <span class="keyword">operator</span>
          <span class="special">+=</span> <span class="special">(</span><span class="identifier">T</span><span class="special">&amp;,</span> <span class="keyword">const</span> <span class="identifier">P</span><span class="special">&amp;)</span></code> are given by two tables, that show
          admissible combinations of types. Row types show instantiations of argument
          type <code class="computeroutput"><span class="identifier">T</span></code>. Columns types show
          show instantiations of argument type <code class="computeroutput"><span class="identifier">P</span></code>.
          If a combination of argument types is possible, the related table cell
          contains the result type of the operation. <a class="link" href="../interface/function_synopsis.html#element_type">Placeholders</a>
          <a class="link" href="../interface/function_synopsis.html#element_type"><span class="bold"><strong>e</strong></span></a>
          <a class="link" href="../interface/function_synopsis.html#interval_type"><span class="bold"><strong>i</strong></span></a>
          <a class="link" href="../interface/function_synopsis.html#element_mapping_type"><span class="bold"><strong>b</strong></span></a>
          <a class="link" href="../interface/function_synopsis.html#interval_mapping_type"><span class="bold"><strong>p</strong></span></a>
          <a class="link" href="../interface/function_synopsis.html#itl_set_type"><span class="bold"><strong>s</strong></span></a>
          <a class="link" href="../interface/function_synopsis.html#interval_set_types"><span class="bold"><strong>S</strong></span></a>
          <a class="link" href="../interface/function_synopsis.html#itl_map_type"><span class="bold"><strong>m</strong></span></a>
          <a class="link" href="../interface/function_synopsis.html#interval_map_types"><span class="bold"><strong>M</strong></span></a>
          will be used to denote <span class="emphasis"><em>elements, intervals, element value pairs,
          interval value pairs, element sets, interval sets, element maps</em></span>
          and <span class="emphasis"><em>interval maps</em></span>. The first table shows the overloads
          of <code class="computeroutput"><span class="special">+=</span></code> for <span class="emphasis"><em>element
          containers</em></span> the second table refers to <span class="emphasis"><em>interval containers</em></span>.
        </p>
<p>
          
</p>
<pre class="programlisting"><span class="comment">// overload tables for             element containers:     interval containers:  
</span><span class="identifier">T</span><span class="special">&amp;</span> <span class="keyword">operator</span> <span class="special">+=</span> <span class="special">(</span><span class="identifier">T</span><span class="special">&amp;,</span> <span class="keyword">const</span> <span class="identifier">P</span><span class="special">&amp;)</span>      <span class="special">+=</span> <span class="special">|</span> <span class="identifier">e</span> <span class="identifier">b</span> <span class="identifier">s</span> <span class="identifier">m</span>            <span class="special">+=</span> <span class="special">|</span> <span class="identifier">e</span> <span class="identifier">i</span> <span class="identifier">b</span> <span class="identifier">p</span> <span class="identifier">S</span> <span class="identifier">M</span>    
                                   <span class="special">---+--------</span>            <span class="special">---+------------</span>    
                                   <span class="identifier">s</span>  <span class="special">|</span> <span class="identifier">s</span>   <span class="identifier">s</span>              <span class="identifier">S</span>  <span class="special">|</span> <span class="identifier">S</span> <span class="identifier">S</span>     <span class="identifier">S</span>       
                                   <span class="identifier">m</span>  <span class="special">|</span>   <span class="identifier">m</span>   <span class="identifier">m</span>            <span class="identifier">M</span>  <span class="special">|</span>     <span class="identifier">M</span> <span class="identifier">M</span>   <span class="identifier">M</span>    
</pre>
<p>
        </p>
<p>
          For the definition of admissible overloads we separate <span class="emphasis"><em>element
          containers</em></span> from <span class="emphasis"><em>interval containers</em></span>. Within
          each group all combinations of types are supported for an operation, that
          are in line with the <span class="bold"><strong>icl's</strong></span> design and
          the sets of laws, that establish the <span class="bold"><strong>icl's</strong></span>
          <a class="link" href="../semantics.html" title="Semantics">semantics</a>.
        </p>
<p>
          Overloads between <span class="emphasis"><em>element containers</em></span> and <span class="emphasis"><em>interval
          containers</em></span> could also be defined. But this has not been done
          for pragmatical reasons: Each additional combination of types for an operation
          enlarges the space of possible overloads. This makes the overload resolution
          by compilers more complex, error prone and slows down compilation speed.
          Error messages for unresolvable or ambiguous overloads are difficult to
          read and understand. Therefore overloading of namespace global functions
          in the <span class="bold"><strong>icl</strong></span> are limited to a reasonable
          field of combinations, that are described here.
        </p>
</div>
<a name="boost_icl.function_reference.addition.complexity"></a><h5>
<a name="id1156317"></a>
        <a class="link" href="addition.html#boost_icl.function_reference.addition.complexity">Complexity</a>
      </h5>
<p>
        For different combinations of argument types <code class="computeroutput"><span class="identifier">T</span></code>
        and <code class="computeroutput"><span class="identifier">P</span></code> different implementations
        of the <code class="computeroutput"><span class="keyword">operator</span> <span class="special">+=</span></code>
        are selected. These implementations show different complexity characteristics.
        If <code class="computeroutput"><span class="identifier">T</span></code> is a container type,
        the combination of domain elements (<a class="link" href="../interface/function_synopsis.html#element_type"><span class="bold"><strong>e</strong></span></a>) or element value pairs (<a class="link" href="../interface/function_synopsis.html#element_mapping_type"><span class="bold"><strong>b</strong></span></a>) is faster than a combination of intervals
        (<a class="link" href="../interface/function_synopsis.html#interval_type"><span class="bold"><strong>i</strong></span></a>)
        or interval value pairs (<a class="link" href="../interface/function_synopsis.html#interval_mapping_type"><span class="bold"><strong>p</strong></span></a>) which in turn is faster than the combination
        of element or interval containers. The next table shows <span class="emphasis"><em>time complexities</em></span>
        of addition for <span class="bold"><strong>icl's</strong></span> element containers.
      </p>
<p>
        Sizes <code class="computeroutput"><span class="identifier">n</span></code> and <code class="computeroutput"><span class="identifier">m</span></code> are in the complexity statements are
        sizes of objects <code class="computeroutput"><span class="identifier">T</span> <span class="identifier">y</span></code>
        and <code class="computeroutput"><span class="identifier">P</span> <span class="identifier">x</span></code>:
        
</p>
<pre class="programlisting"><span class="identifier">n</span> <span class="special">=</span> <span class="identifier">iterative_size</span><span class="special">(</span><span class="identifier">y</span><span class="special">);</span>
<span class="identifier">m</span> <span class="special">=</span> <span class="identifier">iterative_size</span><span class="special">(</span><span class="identifier">x</span><span class="special">);</span> <span class="comment">//if P is a container type
</span></pre>
<p>
        Note, that for an interval container the number of elements <code class="computeroutput"><span class="identifier">T</span><span class="special">::</span><span class="identifier">size</span></code>
        is different from the number of intervals that you can iterate over. Therefore
        a function <code class="computeroutput"><span class="identifier">T</span><span class="special">::</span><span class="identifier">iterative_size</span><span class="special">()</span></code>
        is used that provides the desired kind of size.
      </p>
<div class="table">
<a name="id1157636"></a><p class="title"><b>Table&#160;1.22.&#160;Time Complexity for inplace Addition on element
      containers</b></p>
<div class="table-contents"><table class="table" summary="Time Complexity for inplace Addition on element
      containers">
<colgroup>
<col>
<col>
<col>
<col>
<col>
</colgroup>
<thead><tr>
<th>
            <p>
              <code class="computeroutput"><span class="identifier">T</span><span class="special">&amp;</span>
              <span class="keyword">operator</span> <span class="special">+=</span>
              <span class="special">(</span><span class="identifier">T</span><span class="special">&amp;</span> <span class="identifier">y</span><span class="special">,</span> <span class="keyword">const</span> <span class="identifier">P</span><span class="special">&amp;</span>
              <span class="identifier">x</span><span class="special">)</span></code>
            </p>
            </th>
<th>
            <p>
              domain<br> type
            </p>
            </th>
<th>
            <p>
              domain<br> mapping<br> type
            </p>
            </th>
<th>
            <p>
              __ch_icl<span class="underline">sets</span><span class="underline">][</span>_ch_icl<span class="underline">maps</span>_
            </p>
            </th>
<td class="auto-generated">&#160;</td>
</tr></thead>
<tbody>
<tr>
<td>
            <p>
              <a href="http://www.cplusplus.com/reference/stl/set/" target="_top"><code class="computeroutput"><span class="identifier">std</span><span class="special">::</span><span class="identifier">set</span></code> </a>
            </p>
            </td>
<td>
            <p>
              <span class="emphasis"><em>O(log n)</em></span>
            </p>
            </td>
<td>
            <p>
            </p>
            </td>
<td>
            <p>
              <span class="emphasis"><em>O(m)</em></span>
            </p>
            </td>
<td>
            <p>
            </p>
            </td>
</tr>
<tr>
<td>
            <p>
              <code class="computeroutput"><a class="link" href="../../boost/icl/map.html" title="Class template map">icl::map</a></code>
            </p>
            </td>
<td>
            <p>
            </p>
            </td>
<td>
            <p>
              <span class="emphasis"><em>O(log n)</em></span>
            </p>
            </td>
<td>
            <p>
            </p>
            </td>
<td>
            <p>
              <span class="emphasis"><em>O(m)</em></span>
            </p>
            </td>
</tr>
</tbody>
</table></div>
</div>
<br class="table-break"><p>
        Time complexity characteristics of inplace addition for interval containers
        is given by this table.
      </p>
<div class="table">
<a name="id1157881"></a><p class="title"><b>Table&#160;1.23.&#160;Time Complexity for inplace Addition on interval
      containers</b></p>
<div class="table-contents"><table class="table" summary="Time Complexity for inplace Addition on interval
      containers">
<colgroup>
<col>
<col>
<col>
<col>
<col>
<col>
<col>
<col>
</colgroup>
<thead><tr>
<th>
            <p>
              <code class="computeroutput"><span class="identifier">T</span><span class="special">&amp;</span>
              <span class="keyword">operator</span> <span class="special">+=</span>
              <span class="special">(</span><span class="identifier">T</span><span class="special">&amp;</span> <span class="identifier">y</span><span class="special">,</span> <span class="keyword">const</span> <span class="identifier">P</span><span class="special">&amp;</span>
              <span class="identifier">x</span><span class="special">)</span></code>
            </p>
            </th>
<th>
            <p>
            </p>
            </th>
<th>
            <p>
              domain<br> type
            </p>
            </th>
<th>
            <p>
              interval<br> type
            </p>
            </th>
<th>
            <p>
              domain<br> mapping<br> type
            </p>
            </th>
<th>
            <p>
              interval<br> mapping<br> type
            </p>
            </th>
<th>
            <p>
              interval<br> sets
            </p>
            </th>
<th>
            <p>
              interval<br> maps
            </p>
            </th>
</tr></thead>
<tbody>
<tr>
<td>
            <p>
              interval_sets
            </p>
            </td>
<td>
            <p>
              <code class="computeroutput"><a class="link" href="../../boost/icl/interval_set.html" title="Class template interval_set">interval_set</a></code><br>
              <code class="computeroutput"><a class="link" href="../../boost/icl/separate_interval_set.html" title="Class template separate_interval_set">separate_interval_set</a></code>
            </p>
            </td>
<td>
            <p>
              <span class="emphasis"><em>O(log n)</em></span>
            </p>
            </td>
<td>
            <p>
              <span class="emphasis"><em>amortized<br> O(log n)</em></span>
            </p>
            </td>
<td>
            <p>
            </p>
            </td>
<td>
            <p>
            </p>
            </td>
<td>
            <p>
              <span class="emphasis"><em>O(m log(n+m))</em></span>
            </p>
            </td>
<td>
            <p>
            </p>
            </td>
</tr>
<tr>
<td>
            <p>
            </p>
            </td>
<td>
            <p>
              <code class="computeroutput"><a class="link" href="../../boost/icl/split_interval_set.html" title="Class template split_interval_set">split_interval_set</a></code>
            </p>
            </td>
<td>
            <p>
              <span class="emphasis"><em>O(log n)</em></span>
            </p>
            </td>
<td>
            <p>
              <span class="emphasis"><em>O(n)</em></span>
            </p>
            </td>
<td>
            <p>
            </p>
            </td>
<td>
            <p>
            </p>
            </td>
<td>
            <p>
              <span class="emphasis"><em>O(m log(n+m))</em></span>
            </p>
            </td>
<td>
            <p>
            </p>
            </td>
</tr>
<tr>
<td>
            <p>
              interval_maps
            </p>
            </td>
<td>
            <p>
            </p>
            </td>
<td>
            <p>
            </p>
            </td>
<td>
            <p>
            </p>
            </td>
<td>
            <p>
              <span class="emphasis"><em>O(log n)</em></span>
            </p>
            </td>
<td>
            <p>
              <span class="emphasis"><em>O(n)</em></span>
            </p>
            </td>
<td>
            <p>
            </p>
            </td>
<td>
            <p>
              <span class="emphasis"><em>O(m log(n+m))</em></span>
            </p>
            </td>
</tr>
</tbody>
</table></div>
</div>
<br class="table-break"><p>
        Since the implementation of element and interval containers is based on the
        <a class="link" href="../implementation.html" title="Implementation">link red-black tree implementation</a>
        of std::AssociativeContainers, we have a logarithmic complexity for addition
        of elements. Addition of intervals or interval value pairs is amortized logarithmic
        for <code class="computeroutput"><a class="link" href="../../boost/icl/interval_set.html" title="Class template interval_set">interval_sets</a></code> and
        <code class="computeroutput"><a class="link" href="../../boost/icl/separate_interval_set.html" title="Class template separate_interval_set">separate_interval_sets</a></code>
        and linear for <code class="computeroutput"><a class="link" href="../../boost/icl/split_interval_set.html" title="Class template split_interval_set">split_interval_sets</a></code>
        and <code class="computeroutput"><a class="link" href="../../boost/icl/interval_map.html" title="Class template interval_map">interval_maps</a></code>.
        Addition is linear for element containers and loglinear for interval containers.
      </p>
<div class="section boost_icl_function_reference_addition_infix_operators" lang="en">
<div class="titlepage"><div><div><h4 class="title">
<a name="boost_icl.function_reference.addition.infix_operators"></a><a class="link" href="addition.html#boost_icl.function_reference.addition.infix_operators" title="Infix operators">Infix
        operators</a>
</h4></div></div></div>
<p>
          The admissible type combinations for infix <code class="computeroutput"><span class="keyword">operator</span>
          <span class="special">+</span></code> are defined by the overload tables
          below.
        </p>
<p>
          
</p>
<pre class="programlisting"><span class="comment">// overload tables for          element containers:     interval containers:
</span><span class="identifier">T</span> <span class="keyword">operator</span> <span class="special">+</span> <span class="special">(</span><span class="identifier">T</span><span class="special">,</span> <span class="keyword">const</span> <span class="identifier">P</span><span class="special">&amp;)</span>      <span class="special">+</span>  <span class="special">|</span> <span class="identifier">e</span> <span class="identifier">b</span> <span class="identifier">s</span> <span class="identifier">m</span>            <span class="special">+</span>  <span class="special">|</span> <span class="identifier">e</span>  <span class="identifier">i</span>  <span class="identifier">b</span>  <span class="identifier">p</span>  <span class="identifier">S1</span> <span class="identifier">S2</span> <span class="identifier">S3</span> <span class="identifier">M1</span> <span class="identifier">M3</span>  
<span class="identifier">T</span> <span class="keyword">operator</span> <span class="special">+</span> <span class="special">(</span><span class="keyword">const</span> <span class="identifier">P</span><span class="special">&amp;,</span> <span class="identifier">T</span><span class="special">)</span>      <span class="special">---+--------</span>            <span class="special">---+---------------------------</span>
                                <span class="identifier">e</span>  <span class="special">|</span>     <span class="identifier">s</span>              <span class="identifier">e</span>  <span class="special">|</span>             <span class="identifier">S1</span> <span class="identifier">S2</span> <span class="identifier">S3</span> 
                                <span class="identifier">b</span>  <span class="special">|</span>       <span class="identifier">m</span>            <span class="identifier">i</span>  <span class="special">|</span>             <span class="identifier">S1</span> <span class="identifier">S2</span> <span class="identifier">S3</span> 
                                <span class="identifier">s</span>  <span class="special">|</span> <span class="identifier">s</span>   <span class="identifier">s</span>              <span class="identifier">b</span>  <span class="special">|</span>                      <span class="identifier">M1</span> <span class="identifier">M3</span>  
                                <span class="identifier">m</span>  <span class="special">|</span>   <span class="identifier">m</span>   <span class="identifier">m</span>            <span class="identifier">p</span>  <span class="special">|</span>                      <span class="identifier">M1</span> <span class="identifier">M3</span>
                                                        <span class="identifier">S1</span> <span class="special">|</span> <span class="identifier">S1</span> <span class="identifier">S1</span>       <span class="identifier">S1</span> <span class="identifier">S2</span> <span class="identifier">S3</span> 
                                                        <span class="identifier">S2</span> <span class="special">|</span> <span class="identifier">S2</span> <span class="identifier">S2</span>       <span class="identifier">S2</span> <span class="identifier">S2</span> <span class="identifier">S3</span> 
                                                        <span class="identifier">S3</span> <span class="special">|</span> <span class="identifier">S3</span> <span class="identifier">S3</span>       <span class="identifier">S3</span> <span class="identifier">S3</span> <span class="identifier">S3</span> 
                                                        <span class="identifier">M1</span> <span class="special">|</span>       <span class="identifier">M1</span> <span class="identifier">M1</span>          <span class="identifier">M1</span> <span class="identifier">M3</span>
                                                        <span class="identifier">M3</span> <span class="special">|</span>       <span class="identifier">M3</span> <span class="identifier">M3</span>          <span class="identifier">M3</span> <span class="identifier">M3</span>
</pre>
<p>
        </p>
</div>
<p>
        <span class="emphasis"><em><span class="bold"><strong>See also . . .</strong></span></em></span>
      </p>
<div class="informaltable"><table class="table">
<colgroup><col></colgroup>
<thead><tr></tr></thead>
<tbody>
<tr><td>
              <p>
                <a class="link" href="subtraction.html" title="Subtraction"><span class="emphasis"><em><span class="bold"><strong>Subtraction</strong></span></em></span></a>
              </p>
              </td></tr>
<tr><td>
              <p>
                <a class="link" href="insertion.html" title="Insertion"><span class="emphasis"><em><span class="bold"><strong>Insertion</strong></span></em></span></a>
              </p>
              </td></tr>
</tbody>
</table></div>
<p>
        <span class="emphasis"><em><span class="bold"><strong>Back to section . . .</strong></span></em></span>
      </p>
<div class="informaltable"><table class="table">
<colgroup><col></colgroup>
<thead><tr></tr></thead>
<tbody>
<tr><td>
              <p>
                <a class="link" href="../interface/function_synopsis.html#function_synopsis_table"><span class="emphasis"><em><span class="bold"><strong>Function
                Synopsis</strong></span></em></span></a>
              </p>
              </td></tr>
<tr><td>
              <p>
                <a class="link" href="../interface.html" title="Interface"><span class="emphasis"><em><span class="bold"><strong>Interface</strong></span></em></span></a>
              </p>
              </td></tr>
</tbody>
</table></div>
</div>
<table xmlns:rev="http://www.cs.rpi.edu/~gregod/boost/tools/doc/revision" width="100%"><tr>
<td align="left"></td>
<td align="right"><div class="copyright-footer">Copyright &#169; 2007 -2010 Joachim Faulhaber<br>Copyright &#169; 1999 -2006 Cortex Software GmbH<p>
        Distributed under the Boost Software License, Version 1.0. (See accompanying
        file LICENSE_1_0.txt or copy at <a href="http://www.boost.org/LICENSE_1_0.txt" target="_top">http://www.boost.org/LICENSE_1_0.txt</a>)
      </p>
</div></td>
</tr></table>
<hr>
<div class="spirit-nav">
<a accesskey="p" href="selection.html"><img src="../../../../../../doc/src/images/prev.png" alt="Prev"></a><a accesskey="u" href="../function_reference.html"><img src="../../../../../../doc/src/images/up.png" alt="Up"></a><a accesskey="h" href="../../index.html"><img src="../../../../../../doc/src/images/home.png" alt="Home"></a><a accesskey="n" href="subtraction.html"><img src="../../../../../../doc/src/images/next.png" alt="Next"></a>
</div>
</body>
</html>
